Tal lọt vào trận chung kết Giải Vô địch Cờ vua Liên Xô năm 1956 và trở thành nhà vô địch trẻ nhất vào năm tiếp theo, khi mới 20 tuổi. Anh không chơi đủ số giải đấu quốc tế cần thiết để có thể đạt danh hiệu Đại kiện tướng nhưng FIDE đã quyết định phá bỏ những giới hạn đó tại Đại hội năm 1957 và đặc cách phong Đại kiện tướng cho Tal vì thành tích vô địch Liên Xô. Tại thời điểm này, cờ vua Liên Xô đang thống trị nền cờ vua thế giới và Tal đã đánh bại một số kỳ thủ hàng đầu thế giới để lên ngôi vô địch.

Tal tham gia đội tuyển cờ vua sinh viên Liên Xô 3 lần, từ 1956 đến 1958, giành 3 huy chương vàng đồng đội và 3 huy chương vàng cá nhân. Anh thắng 19 trận, hòa 8 và không thua trận nào với tỉ lệ thắng là 85.2%.[7]

Anh bảo vệ thành công chức vô địch Liên Xô năm 1958 và tham dự giải Vô địch Cờ vua Thế giới lần đầu tiên. Anh vô địch giải Interzonal 1958 tại Portorož và cùng đội tuyển cờ vua Liên Xô vô địch Olympiad Cờ vua lần thứ 4 liên tiếp tại Munich.